class Disjoinset {
public:
    vector<int> parent;
    vector<int> rank;

    Disjoinset(int n) : parent(n), rank(n,0){
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }

    int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if(rank[rootx] == rank[rooty]){
                rank[rootx]+=1;
            }
        }
    }

};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        unordered_map<string, int> emailaccounts;
        Disjoinset ds(n);
        for(int i=0;i<n;i++){
            int m = accounts[i].size();
            for(int j=1;j<m;j++){
                string email = accounts[i][j];
                if(emailaccounts.find(email)==emailaccounts.end()){
                    emailaccounts[email]=i;
                }else{
                    ds.merge(i,emailaccounts[email]);
                }
            }
        }
        unordered_map<int, vector<string>> td;
        for(auto ac:emailaccounts){
            string email = ac.first;
            int index = ac.second;
            index = ds.find(index);
            td[index].push_back(email);
        }
        vector<vector<string>> res;
        for(const auto& t:td){
            vector<string> email = t.second;
            sort(email.begin(),email.end());
            vector<string> d;
            d.push_back(accounts[t.first][0]);
            d.insert(d.end(),email.begin(),email.end());
            res.push_back(d);
        }
        return res;
    }
};
